package com.lw.leetcode.sort.b;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * b
 * sort
 * 2542. 最大子序列的分数
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/28 10:31
 */
public class MaxScore {

    public long maxScore(int[] nums1, int[] nums2, int k) {
        int length = nums1.length;
        int[][] arr = new int[length][2];
        for (int i = 0; i < length; i++) {
            arr[i][0] = nums1[i];
            arr[i][1] = nums2[i];
        }
        Arrays.sort(arr, (a, b) -> Integer.compare(b[1], a[1]));
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        long sum = 0;
        for (int i = 0; i < k; i++) {
            queue.add(arr[i][0]);
            sum += arr[i][0];
        }
        long max = sum * arr[k - 1][1];
        for (int i = k; i < length; i++) {
            sum -= queue.poll();
            queue.add(arr[i][0]);
            sum += arr[i][0];
            max = Math.max(max, sum * arr[i][1]);

        }
        return max;
    }

}
